# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName : insert_sort2.py
# @Time     : 2024/1/28 23:17
# @Author   : Robot-Zsj
"""
description: 
"""


def insert_sort2(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        high = i - 1
        low = 0
        while low <= high:
            mid = int((low + high) / 2)
            if key >= nums[mid]:
                low = mid + 1
            if key < nums[mid]:
                high = mid - 1
        j = i - 1
        while j >= low:
            nums[j + 1] = nums[j]
            j -= 1
        nums[low] = key
    return nums


print(insert_sort2([50, 36, 66, 76, 95, 12, 25]))
